package com.arron.algorithm.leetcodetop100.回溯;


import java.util.ArrayList;
import java.util.List;

/**
 *  动态规划解法
 *  @see com.arron.algorithm.leetcodetop100.动态规划.背包问题.零钱兑换II
 *
 */

public class 零钱兑换II {


    int count;

    List<List<Integer>> resList;
    public int change(int amount, int[] coins) {
        resList = new ArrayList<>();
        change(amount,coins,new ArrayList<>(),0);
        System.out.println(resList);
        return count;
    }

    public void change(int amount, int[] coins, List<Integer> chooseList,int start) {

        if (amount<0){
            return;
        }
        if (amount == 0){
            count++;
            resList.add(new ArrayList<>(chooseList));
        }
        for (int i = start; i < coins.length; i++) {
            amount = amount - coins[i];
            chooseList.add(coins[i]);
            change(amount, coins, chooseList,i);
            amount = amount + coins[i];
            chooseList.remove(chooseList.size() - 1);
        }
    }


    public static void main(String[] args) {
        零钱兑换II changge = new 零钱兑换II();

        int[] nums = {1,2,5};
        changge.change(5, nums);
    }




}
